package main

import (
	"container/list"
	"fmt"
)

/*
在数组中找到两个数字之和等于给定值的数字，结果返回两个数字在数组中的下标。示例:
	Given nums = [2, 7, 11, 15], target = 9,
	Because nums[0] + nums[1] = 2 + 7 = 9,
	return [0, 1]
*/
func main() {

	/*
		解题思路：时间复杂度是 O(n)。顺序扫描数组，对每一个元素，在 map 中找能组合给定值的另一半数字，如果找到了，直接返回两个数字的下标即可。
				如果找不到，就把这个数字存入 map 中，等待扫到“另一半”数字的时候，再取出来返回结果
	*/

	nums := []int{1, 2, 3, 4, 5, 6}
	target := 60
	sum := twoSum(nums, target)
	if sum.Front() == nil {
		fmt.Println("找不到这样的结果")
		return
	}
	for front := sum.Front(); front != nil; front = front.Next() {
		fmt.Println(front.Value)
	}
}

func twoSum(nums []int, target int) list.List {

	// 使用列表保存返回值
	l := list.List{}
	m := make(map[int]int)
	for i := 0; i < len(nums); i++ {
		// 找到遍历值的另一半数字，并在map中寻找是否存在，存在则保存在返回列表中
		i2 := target - nums[i]
		if _, ok := m[i2]; ok {
			l.PushBack([]int{m[i2], i})
		}
		// 使用map保存每次遍历值
		m[nums[i]] = i
	}

	return l
}
